const tree = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                {
                    val: 'd',
                    children: []
                },
                {
                    val: 'e',
                    children: []
                }
            ]
        },
        {
            val: 'c',
            children: [
                {
                    val: 'f',
                    children: []
                },
                {
                    val: 'g',
                    children: []
                }
            ]
        }
    ]
}
// 深度遍历
const dfs = root => {
    console.log(root.val)
    root.children.forEach(dfs)
}
dfs(tree)
console.log('-----------------')
// 广度遍历
const bfs = root => {
    const q = [root]
    while (q.length > 0) {
        const n = q.shift()
        console.log(n.val)
        n.children.forEach(child => {
            q.push(child)
        })
    }
}
bfs(tree)
console.log('-----------------')

const tree2 = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null
        },
        right: {
            val: 5,
            left: null,
            right: null
        }
    },
    right: {
        val: 3,
        left: {
            val: 6,
            left: null,
            right: null
        },
        right: {
            val: 7,
            left: null,
            right: null
        }
    }
}
// 递归版
console.log('递归开始-----------------')
// 二叉树先序遍历
const preorder = root => {
    if (!root) return
    console.log(root.val)
    preorder(root.left)
    preorder(root.right)
}
preorder(tree2)
console.log('-----------------')
// 二叉树中序遍历
const inorder = root => {
    if (!root) return
    inorder(root.left)
    console.log(root.val)
    inorder(root.right)
}
inorder(tree2)
console.log('-----------------')
// 二叉树后序遍历
const postorder = root => {
    if (!root) return
    postorder(root.left)
    postorder(root.right)
    console.log(root.val)
}
postorder(tree2)
// 非递归版
console.log('非递归开始-----------------')
// 二叉树先序遍历
const preorder2 = root => {
    if (!root) return
    const stack = [root]
    while (stack.length) {
        const n = stack.pop()
        console.log(n.val)
        if (n.right) stack.push(n.right)
        if (n.left) stack.push(n.left)
    }
}
preorder2(tree2)
console.log('-----------------')
// 二叉树中序遍历
const inorder2 = root => {
    if (!root) return
    const stack = []
    let p = root
    while (stack.length || p) {
        while (p) {
            stack.push(p)
            p = p.left
        }
        const n = stack.pop()
        console.log(n.val)
        p = n.right
    }
}
inorder2(tree2)
console.log('-----------------')
// 二叉树后序遍历
const postorder2 = root => {
    if (!root) return
    const outputStack = []
    const stack = [root]
    while (stack.length) {
        const n = stack.pop()
        outputStack.push(n)
        if (n.left) stack.push(n.left)
        if (n.right) stack.push(n.right)
    }
    while (outputStack.length) {
        const n = outputStack.pop()
        console.log(n.val)
    }
}
postorder2(tree2)
console.log('-----------------')
// 遍历JSON的所有节点值
const json = {
    a: {b: {c: 1}},
    d: [1, 2]
}
const dfsJson = (n, path) => {
    console.log('n:' + JSON.stringify(n), 'path:' + path)
    Object.keys(n).forEach(k => {
        dfsJson(n[k], path.concat(k))
    })
}
dfsJson(json, [])
console.log('-----------------')



